import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class T6 {
    static class Course {
        String name;
        int startTime;
        int endTime;
        int importance;    // 重要性（1-10）
        int credits;       // 学分（1-5）
        int difficulty;    // 难度（1-5）
        boolean hasExam;   // 是否需要考试
        double priority;   // 优先级 = (重要性 × 学分 / 难度) + (无考试奖励)

        Course(String name, int startTime, int endTime, int importance, int credits, int difficulty, boolean hasExam) {
            this.name = name;
            this.startTime = startTime;
            this.endTime = endTime;
            this.importance = importance;
            this.credits = credits;
            this.difficulty = difficulty;
            this.hasExam = hasExam;
            this.priority = (importance * credits) / (double) difficulty + (hasExam ? 0 : 10);
        }
    }

    // 检查课程是否与当前课程表兼容
    private static boolean isCompatible(ArrayList<Course> schedule, Course newCourse) {
        for (Course c : schedule) {
            if (newCourse.startTime < c.endTime && newCourse.endTime > c.startTime) {
                return false; // 时间冲突
            }
        }
        return true;
    }

    // 计算课程表的总学分
    private static int calculateTotalCredits(ArrayList<Course> schedule) {
        int total = 0;
        for (Course c : schedule) {
            total += c.credits;
        }
        return total;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("欢迎使用高级课程表优化系统！");
        System.out.println("本系统将优化课程安排以满足学分并提升优先级。");

        // 输入目标学分和课程数量
        System.out.print("请输入这学期需要修满的最低学分: ");
        int targetCredits = scanner.nextInt();
        scanner.nextLine();
        System.out.print("请输入课程数量 n: ");
        int n = scanner.nextInt();
        scanner.nextLine();

        // 输入课程信息
        Course[] courses = new Course[n];
        System.out.println("请依次输入每门课程的详细信息：");
        for (int i = 0; i < n; i++) {
            System.out.println("课程 " + (i + 1) + ":");
            System.out.print("课程名称: ");
            String name = scanner.nextLine();
            System.out.print("开始时间: ");
            int start = scanner.nextInt();
            System.out.print("结束时间: ");
            int end = scanner.nextInt();
            System.out.print("重要性 (1-10): ");
            int importance = scanner.nextInt();
            System.out.print("学分 (1-5): ");
            int credits = scanner.nextInt();
            System.out.print("难度 (1-5): ");
            int difficulty = scanner.nextInt();
            System.out.print("是否需要考试 (y/n): ");
            String examInput = scanner.next();
            boolean hasExam = examInput.equalsIgnoreCase("y");
            scanner.nextLine();
            courses[i] = new Course(name, start, end, importance, credits, difficulty, hasExam);
        }

        // 按结束时间排序
        Arrays.sort(courses, Comparator.comparingInt(c -> c.endTime));

        // 第一阶段：动态贪心选择，确保学分达标
        ArrayList<Course> bestSchedule = new ArrayList<>();
        int bestCredits = 0;
        for (int start = 0; start < n; start++) { // 尝试不同的起点
            ArrayList<Course> tempSchedule = new ArrayList<>();
            tempSchedule.add(courses[start]);
            int lastEndTime = courses[start].endTime;
            int totalCredits = courses[start].credits;

            for (int i = start + 1; i < n && totalCredits < targetCredits; i++) {
                if (courses[i].startTime >= lastEndTime) {
                    tempSchedule.add(courses[i]);
                    lastEndTime = courses[i].endTime;
                    totalCredits += courses[i].credits;
                }
            }

            if (totalCredits > bestCredits) {
                bestSchedule = new ArrayList<>(tempSchedule);
                bestCredits = totalCredits;
            }
        }

        // 如果学分仍未达标，提示用户
        if (bestCredits < targetCredits) {
            System.out.println("警告：无法通过贪心选择满足学分要求，将尝试优化。");
        }

        // 第二阶段：优化优先级（允许多课程替换）
        Arrays.sort(courses, Comparator.comparingDouble(c -> -c.priority)); // 按优先级降序排序
        for (Course current : courses) {
            if (!bestSchedule.contains(current)) {
                ArrayList<Course> tempSchedule = new ArrayList<>(bestSchedule);
                int tempCredits = calculateTotalCredits(tempSchedule);

                // 移除所有与当前课程冲突的课程
                for (int j = tempSchedule.size() - 1; j >= 0; j--) {
                    if (tempSchedule.get(j).endTime > current.startTime &&
                            tempSchedule.get(j).startTime < current.endTime &&
                            current.priority > tempSchedule.get(j).priority) {
                        tempCredits -= tempSchedule.get(j).credits;
                        tempSchedule.remove(j);
                    }
                }

                // 如果移除后学分仍够，且时间兼容，则加入
                if (tempCredits + current.credits >= targetCredits && isCompatible(tempSchedule, current)) {
                    tempSchedule.add(current);
                    bestSchedule = tempSchedule;
                    bestCredits = tempCredits + current.credits;
                }
            }
        }

        // 输出结果
        System.out.println("\n优化后的课程表如下：");
        System.out.println("课程名称\t开始时间\t结束时间\t重要性\t学分\t难度\t需要考试\t优先级");
        System.out.println("------------------------------------------------------------");
        bestSchedule.sort(Comparator.comparingInt(c -> c.startTime)); // 按开始时间排序输出
        for (Course c : bestSchedule) {
            System.out.printf("%s\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%s\t\t%.2f%n",
                    c.name, c.startTime, c.endTime, c.importance, c.credits,
                    c.difficulty, c.hasExam ? "是" : "否", c.priority);
        }
        System.out.println("共安排了 " + bestSchedule.size() + " 门课程，总学分：" + bestCredits);
        if (bestCredits >= targetCredits) {
            System.out.println("恭喜！总学分达到目标：" + targetCredits);
        } else {
            System.out.println("抱歉，无法安排足够的课程达到目标学分 " + targetCredits + "，请检查输入课程！");
        }

        scanner.close();
    }
}